<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <title>数据结构和算法6-非线性-图 | iworkh blog</title>
  
    <meta name="keywords" content=" 结构和算法 ">
  
  <meta name="description" content="数据结构和算法6-非线性-图 | iworkh blog">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="个人简介沐雨云楼，程序员一名。 喜欢研究技术，主要从事JAVA、微服务、大数据领域。 联系方式 QQ : 157162006 邮箱 :157162006@qq.com">
<meta property="og:type" content="website">
<meta property="og:title" content="关于">
<meta property="og:url" content="https://iworkh.gitee.io/blog/about/index.html">
<meta property="og:site_name" content="iworkh blog">
<meta property="og:description" content="个人简介沐雨云楼，程序员一名。 喜欢研究技术，主要从事JAVA、微服务、大数据领域。 联系方式 QQ : 157162006 邮箱 :157162006@qq.com">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2020-05-17T07:22:16.000Z">
<meta property="article:modified_time" content="2020-09-12T13:21:47.523Z">
<meta property="article:author" content="沐雨云楼">
<meta property="article:tag" content="iworkh">
<meta property="article:tag" content="沐雨云楼">
<meta property="article:tag" content="blog">
<meta name="twitter:card" content="summary">


<link rel="icon" href="/blog/img/iwork.svg">

<link href="/blog/css/style.css?v=1.0.1" rel="stylesheet">

<link href="/blog/css/hl_theme/atom-light.css?v=1.0.1" rel="stylesheet">

<link href="//cdn.bootcdn.net/ajax/libs/animate.css/4.1.0/animate.min.css" rel="stylesheet">
<link href="//cdn.bootcdn.net/ajax/libs/font-awesome/5.13.0/js/fontawesome.min.js" rel="stylesheet">

<script src="//cdn.bootcdn.net/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="/blog/js/jquery.autocomplete.min.js?v=1.0.1" ></script>
<script src="/blog/js/titleTip.js?v=1.0.1" ></script>

<script src="//cdn.bootcdn.net/ajax/libs/highlight.js/10.0.3/highlight.min.js"></script>
<script>
    hljs.initHighlightingOnLoad();
</script>

<script src="//cdn.bootcdn.net/ajax/libs/nprogress/0.2.0/nprogress.min.js"></script>



<script src="//cdn.bootcdn.net/ajax/libs/jquery-cookie/1.4.1/jquery.cookie.min.js" ></script>

<script src="/blog/js/iconfont.js?v=1.0.1" ></script>

<meta name="generator" content="Hexo 4.2.1"></head>
<div style="display: none">
  <input class="theme_disqus_on" value="false">
  <input class="theme_preload_comment" value="false">
  <input class="theme_blog_path" value="/blog">
</div>




<body>
<aside class="nav">
    <div class="nav-left">
        <a href="/blog/" class="avatar_target">
    <img class="avatar" src="/blog/img/iwork.svg" />
</a>
<div class="author">
    <span>沐雨云楼</span>
</div>

<div class="icon">
    
        
        <a title="github" href="https://gitee.com/iworkh" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-github"></use>
                </svg>
            
        </a>
        
    
        
        <a title="csdn" href="https://blog.csdn.net/u011622109" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-csdn"></use>
                </svg>
            
        </a>
        
    
        
        <a title="email" href="mailto:157162006@qq.com" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-email"></use>
                </svg>
            
        </a>
        
    
        
        <a title="qq" href="http://wpa.qq.com/msgrd?v=3&uin=157162006&site=qq&menu=yes" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-qq"></use>
                </svg>
            
        </a>
        
    
        
        <a title="kugou" href="https://www.kugou.com/" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-kugou"></use>
                </svg>
            
        </a>
        
    
        
        <a title="neteasemusic" href="https://music.163.com/" target="_blank">
            
                <svg class="iconfont-svg" aria-hidden="true">
                    <use xlink:href="#icon-neteasemusic"></use>
                </svg>
            
        </a>
        
    
</div>



<a class="more-menus">更多菜单</a>


<ul>
    <li><div class="all active">全部文章<small>(85)</small></div></li>
    
        
            
            <li><div data-rel="手册"><i class="fold iconfont icon-right"></i>手册<small>(2)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="iworkh">iworkh<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="pgmanor">pgmanor<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="工具"><i class="fold iconfont icon-right"></i>工具<small>(16)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="git">git<small>(2)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="github">github<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="hexo">hexo<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="idea">idea<small>(2)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="markdowm">markdowm<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="maven">maven<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="有道云">有道云<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="java"><i class="fold iconfont icon-right"></i>java<small>(20)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="dao">dao<small>(6)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="jvm">jvm<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="test">test<small>(5)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="tools">tools<small>(3)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="并发">并发<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="微服务"><i class="fold iconfont icon-right"></i>微服务<small>(6)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="spring">spring<small>(2)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="springboot">springboot<small>(3)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="架构">架构<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="大数据"><i class="fold iconfont icon-right"></i>大数据<small>(4)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="hadoop">hadoop<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="spark">spark<small>(3)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="web"><i class="fold iconfont icon-right"></i>web<small>(3)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="vue">vue<small>(2)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="db"><i class="fold iconfont icon-right"></i>db<small>(4)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="mysql">mysql<small>(3)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="redis">redis<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="ai">ai<small>(4)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="python"><i class="fold iconfont icon-right"></i>python<small>(8)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="tornado">tornado<small>(3)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="linux"><i class="fold iconfont icon-right"></i>linux<small>(2)</small></div>
                
                    <ul class="sub hide">
                        
                        <li><div data-rel="docker">docker<small>(1)</small></div>
                            
                        </li>
                            
                        <li><div data-rel="nginx">nginx<small>(1)</small></div>
                            
                        </li>
                            
                    </ul>
                
            </li>
            
        
    
        
            
            <li><div data-rel="windows">windows<small>(3)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="结构和算法">结构和算法<small>(8)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="面试">面试<small>(2)</small></div>
                
            </li>
            
        
    
        
            
            <li><div data-rel="其他">其他<small>(1)</small></div>
                
            </li>
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
        
            
        
    
</ul>
<div class="left-bottom">
    <div class="menus">
    
    
    
    <a class="dynamic-menu " target="_blank"  href="https://pgmanor.gitee.io/blog/">pgmanor</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://www.iworkh.com/manualIt/Category/scopeDev/">iworkh</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://gitee.com/iworkh">gitee</a>
    
    </div>
    <div><a class="about  hasFriend  site_url"  href="/blog/about">关于</a><a style="width: 50%"  class="friends">友链</a></div>
</div>
<input type="hidden" id="iworkh_site_posts_number" value="85">
<input type="hidden" id="iworkh_site_word_count" value="197.8k">
<div style="display: none">
    <span id="busuanzi_value_site_uv"></span>
    <span id="busuanzi_value_site_pv"></span>
</div>

    </div>
    <div class="nav-right">
        <div class="friends-area">
    <div class="friends-title">
        友情链接
        <i class="back-title-list"></i>
    </div>
    <div class="friends-content">
        <ul>
            
            <li><a target="_blank" href="https://www.iworkh.com">iworkh</a></li>
            
            <li><a target="_blank" href="https://www.iworkh.com/download/share/">下载地址</a></li>
            
            <li><a target="_blank" href="http://yelog.org/">叶落阁</a></li>
            
        </ul>
    </div>
</div>
        <div class="title-list">
    <form onkeydown="if(event.keyCode === 13){return false;}">
        <input id="local-search-input" class="search" type="text" placeholder="in: 开头全文搜索" />
        <i class="cross"></i>
        <span>
            <label for="tagswitch">T:</label>
            <input id="tagswitch" type="checkbox" style="display: none" />
            <i id="tagsWitchIcon"></i>
        </span>
    </form>
    <div class="tags-list">
    
    <li class="article-tag-list-item">
        <a class="color3">ai</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">attr</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">aysnc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">beanmap</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">bigdecimal</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">blog</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">chrome</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">dict</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">dll</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">docker</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">domain</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">fastjson</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">func</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">git</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">github</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">hadoop</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">hexo</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">idea</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">iworkh</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">jackson</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">java</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">jdni</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">jfinalshell</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">joplin</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">JPA</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">lock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">markdowm</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">maven</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">mock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">mq</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">mycat</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">mysql</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">nginx</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">notebook</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">plan</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">powermock</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color2">python</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">redis</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">rest</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">sharding-jdbc</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">spark</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">springboot</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">test</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">tool</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">tools</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">tornado</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">transactional</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">web</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">windows</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">wtforms</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">zookeeper</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">分库分表</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">分页</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">命令</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">工具</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">并发</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">序列化</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">微服务</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">性能分析</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">手册</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color4">有道云</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">标签</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">模板</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color5">百度云盘</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color1">结构和算法</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">计划</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">迁移</a>
    </li>
    
    <li class="article-tag-list-item">
        <a class="color3">面试</a>
    </li>
    
    <div class="clearfix"></div>
</div>

    
    <div id="local-search-result">

    </div>
    
    <nav id="title-list-nav">
        
        <a id="top" class="手册 pgmanor "
           href="/blog/2020/12/15/redirect-to-pgmanor/"
           data-tag="迁移"
           data-author="沐雨云楼" >
            <span class="post-title" title="😘博客迁移">😘博客迁移</span>
            <span class="post-date" title="2020-12-15 23:47:55">2020/12/15</span>
        </a>
        
        <a id="top" class="手册 iworkh "
           href="/blog/2020/05/27/manual-iworkh/"
           data-tag="手册,iworkh"
           data-author="沐雨云楼" >
            <span class="post-title" title="iworkh所有手册">iworkh所有手册</span>
            <span class="post-date" title="2020-05-27 21:37:04">2020/05/27</span>
        </a>
        
        <a id="top" class="微服务 springboot "
           href="/blog/2020/06/27/spring_boot_all_resources/"
           data-tag="springboot"
           data-author="沐雨云楼" >
            <span class="post-title" title="Spring Boot全网优质教程汇总">Spring Boot全网优质教程汇总</span>
            <span class="post-date" title="2020-06-27 17:43:13">2020/06/27</span>
        </a>
        
        <a id="top" class="工具 "
           href="/blog/2020/06/22/baidu-pandisk-share/"
           data-tag="百度云盘"
           data-author="沐雨云楼" >
            <span class="post-title" title="百度云盘分享链接">百度云盘分享链接</span>
            <span class="post-date" title="2020-06-22 18:38:21">2020/06/22</span>
        </a>
        
        <a id="top" class="工具 "
           href="/blog/2020/06/21/tool_blogs_all/"
           data-tag="blog"
           data-author="沐雨云楼" >
            <span class="post-title" title="优质博客和文章">优质博客和文章</span>
            <span class="post-date" title="2020-06-21 20:02:14">2020/06/21</span>
        </a>
        
        <a id="top" class="java jvm "
           href="/blog/2020/06/04/java-online-analysis/"
           data-tag="性能分析"
           data-author="沐雨云楼" >
            <span class="post-title" title="JAVA线上故障排查全套路">JAVA线上故障排查全套路</span>
            <span class="post-date" title="2020-06-04 20:34:05">2020/06/04</span>
        </a>
        
        <a id="top" class="工具 idea "
           href="/blog/2020/05/31/jetbrains-idea/"
           data-tag="工具,idea"
           data-author="沐雨云楼" >
            <span class="post-title" title="idea使用技巧">idea使用技巧</span>
            <span class="post-date" title="2020-05-31 16:12:30">2020/05/31</span>
        </a>
        
        <a id="top" class="工具 有道云 "
           href="/blog/2020/05/18/youdao_config_edit/"
           data-tag="工具,有道云"
           data-author="沐雨云楼" >
            <span class="post-title" title="有道云配置修改">有道云配置修改</span>
            <span class="post-date" title="2020-05-18 21:37:04">2020/05/18</span>
        </a>
        
        <a id="top" class="web "
           href="/blog/2020/06/01/web-tools/"
           data-tag="web,tool"
           data-author="沐雨云楼" >
            <span class="post-title" title="前端常用工具">前端常用工具</span>
            <span class="post-date" title="2020-06-01 21:37:04">2020/06/01</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/10/25/tool-linux-jfinalshell/"
           data-tag="jfinalshell"
           data-author="沐雨云楼" >
            <span class="post-title" title="linux连接工具jfinalshell">linux连接工具jfinalshell</span>
            <span class="post-date" title="2020-10-25 10:24:59">2020/10/25</span>
        </a>
        
        <a  class="微服务 springboot "
           href="/blog/2020/10/06/spring-boot-multi-profiles/"
           data-tag="springboot"
           data-author="沐雨云楼" >
            <span class="post-title" title="springboot多环境配置打包">springboot多环境配置打包</span>
            <span class="post-date" title="2020-10-06 21:36:42">2020/10/06</span>
        </a>
        
        <a  class="web vue "
           href="/blog/2020/10/06/vue_springboot_package_publish/"
           data-tag="maven"
           data-author="沐雨云楼" >
            <span class="post-title" title="vue+springboot打包发布">vue+springboot打包发布</span>
            <span class="post-date" title="2020-10-06 14:22:29">2020/10/06</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/10/06/java-jpa-query/"
           data-tag="JPA"
           data-author="沐雨云楼" >
            <span class="post-title" title="JPA自定义sql">JPA自定义sql</span>
            <span class="post-date" title="2020-10-06 10:20:38">2020/10/06</span>
        </a>
        
        <a  class="微服务 spring "
           href="/blog/2020/10/03/spring-pageable/"
           data-tag="分页"
           data-author="沐雨云楼" >
            <span class="post-title" title="vue+springboot分页交互">vue+springboot分页交互</span>
            <span class="post-date" title="2020-10-03 11:08:21">2020/10/03</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/10/02/chrome-plugin/"
           data-tag="chrome"
           data-author="沐雨云楼" >
            <span class="post-title" title="chrome插件">chrome插件</span>
            <span class="post-date" title="2020-10-02 10:11:31">2020/10/02</span>
        </a>
        
        <a  class="windows "
           href="/blog/2020/10/01/windows-less-dll/"
           data-tag="dll"
           data-author="沐雨云楼" >
            <span class="post-title" title="windows缺少dll">windows缺少dll</span>
            <span class="post-date" title="2020-10-01 20:22:28">2020/10/01</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/09/13/java-base-bigdecimal/"
           data-tag="bigdecimal"
           data-author="沐雨云楼" >
            <span class="post-title" title="BigDecimal正确使用了吗?">BigDecimal正确使用了吗?</span>
            <span class="post-date" title="2020-09-13 10:28:54">2020/09/13</span>
        </a>
        
        <a  class="windows "
           href="/blog/2020/09/12/windows-dev-install/"
           data-tag="windows"
           data-author="沐雨云楼" >
            <span class="post-title" title="windows开发环境安装">windows开发环境安装</span>
            <span class="post-date" title="2020-09-12 21:39:01">2020/09/12</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/09/06/tool-notebook-joplin/"
           data-tag="joplin"
           data-author="沐雨云楼" >
            <span class="post-title" title="joplin笔记">joplin笔记</span>
            <span class="post-date" title="2020-09-06 20:50:55">2020/09/06</span>
        </a>
        
        <a  class="web vue "
           href="/blog/2020/09/05/vue-element-admin/"
           data-tag="web"
           data-author="沐雨云楼" >
            <span class="post-title" title="vue element admin开发">vue element admin开发</span>
            <span class="post-date" title="2020-09-05 11:01:38">2020/09/05</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/09/05/tool-notebook/"
           data-tag="notebook"
           data-author="沐雨云楼" >
            <span class="post-title" title="常见笔记软件">常见笔记软件</span>
            <span class="post-date" title="2020-09-05 10:54:34">2020/09/05</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/30/java-dao-shardingSphere/"
           data-tag="sharding-jdbc"
           data-author="沐雨云楼" >
            <span class="post-title" title="分库分表中间件-ShardingSphere">分库分表中间件-ShardingSphere</span>
            <span class="post-date" title="2020-08-30 21:52:45">2020/08/30</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/30/java-dao-mycat/"
           data-tag="mycat"
           data-author="沐雨云楼" >
            <span class="post-title" title="分库分表中间件-MyCat">分库分表中间件-MyCat</span>
            <span class="post-date" title="2020-08-30 15:01:59">2020/08/30</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/30/java-dao-sharding-db/"
           data-tag="分库分表"
           data-author="沐雨云楼" >
            <span class="post-title" title="分库分表中间件-开源产品">分库分表中间件-开源产品</span>
            <span class="post-date" title="2020-08-30 09:37:18">2020/08/30</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/08/29/java-jndi/"
           data-tag="jdni"
           data-author="沐雨云楼" >
            <span class="post-title" title="JNDI">JNDI</span>
            <span class="post-date" title="2020-08-29 17:12:03">2020/08/29</span>
        </a>
        
        <a  class="工具 git "
           href="/blog/2020/08/27/tool-git-setting/"
           data-tag="git"
           data-author="沐雨云楼" >
            <span class="post-title" title="git配置">git配置</span>
            <span class="post-date" title="2020-08-27 21:30:17">2020/08/27</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/08/23/java-powermock/"
           data-tag="powermock"
           data-author="沐雨云楼" >
            <span class="post-title" title="powermock测试框架">powermock测试框架</span>
            <span class="post-date" title="2020-08-23 12:45:17">2020/08/23</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/08/23/java-mockito/"
           data-tag="mock"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍mockito测试框架">👍mockito测试框架</span>
            <span class="post-date" title="2020-08-23 10:45:17">2020/08/23</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/08/22/java-test-ng/"
           data-tag="test"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍TestNG一篇足以">👍TestNG一篇足以</span>
            <span class="post-date" title="2020-08-22 18:37:28">2020/08/22</span>
        </a>
        
        <a  class="db mysql "
           href="/blog/2020/08/19/mysql-common-sql/"
           data-tag="mysql"
           data-author="沐雨云楼" >
            <span class="post-title" title="mysql常用sql">mysql常用sql</span>
            <span class="post-date" title="2020-08-19 21:30:00">2020/08/19</span>
        </a>
        
        <a  class="db mysql "
           href="/blog/2020/08/19/mysql-windows-zip-install/"
           data-tag="mysql"
           data-author="沐雨云楼" >
            <span class="post-title" title="mysql zip在windows上安装">mysql zip在windows上安装</span>
            <span class="post-date" title="2020-08-19 21:00:47">2020/08/19</span>
        </a>
        
        <a  class="工具 idea "
           href="/blog/2020/08/15/jetbrains-crack/"
           data-tag="工具,idea"
           data-author="沐雨云楼" >
            <span class="post-title" title="jetbrains全家桶破解">jetbrains全家桶破解</span>
            <span class="post-date" title="2020-08-15 19:22:33">2020/08/15</span>
        </a>
        
        <a  class="工具 git "
           href="/blog/2020/07/10/tool-git-error-name-too-long/"
           data-tag="git"
           data-author="沐雨云楼" >
            <span class="post-title" title="git文件名太长">git文件名太长</span>
            <span class="post-date" title="2020-07-10 12:03:02">2020/07/10</span>
        </a>
        
        <a  class="db mysql "
           href="/blog/2020/07/04/mysql-lock-unlock-table/"
           data-tag="lock"
           data-author="沐雨云楼" >
            <span class="post-title" title="mysql数据库锁查询和释放">mysql数据库锁查询和释放</span>
            <span class="post-date" title="2020-07-04 21:46:54">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-sort/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法8-排序">数据结构和算法8-排序</span>
            <span class="post-date" title="2020-07-04 18:49:12">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-search/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法7-搜索">数据结构和算法7-搜索</span>
            <span class="post-date" title="2020-07-04 17:48:19">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-graph/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法6-非线性-图">数据结构和算法6-非线性-图</span>
            <span class="post-date" title="2020-07-04 16:09:47">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-tree/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法5-非线性-树">数据结构和算法5-非线性-树</span>
            <span class="post-date" title="2020-07-04 15:09:47">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-linear-queue/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法4-线性-队列">数据结构和算法4-线性-队列</span>
            <span class="post-date" title="2020-07-04 14:10:22">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-linear-stack/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法3-线性-栈">数据结构和算法3-线性-栈</span>
            <span class="post-date" title="2020-07-04 13:00:17">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-linear-list/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法2-线性-链">数据结构和算法2-线性-链</span>
            <span class="post-date" title="2020-07-04 11:32:12">2020/07/04</span>
        </a>
        
        <a  class="结构和算法 "
           href="/blog/2020/07/04/data-structures-algorithms-info/"
           data-tag="结构和算法"
           data-author="沐雨云楼" >
            <span class="post-title" title="数据结构和算法1-介绍">数据结构和算法1-介绍</span>
            <span class="post-date" title="2020-07-04 10:10:40">2020/07/04</span>
        </a>
        
        <a  class="大数据 spark "
           href="/blog/2020/06/30/spark-install-windows/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="spark开发环境搭建">spark开发环境搭建</span>
            <span class="post-date" title="2020-06-30 19:24:51">2020/06/30</span>
        </a>
        
        <a  class="大数据 hadoop "
           href="/blog/2020/06/30/hadoop-install-windows/"
           data-tag="hadoop"
           data-author="沐雨云楼" >
            <span class="post-title" title="hadoop开发环境搭建">hadoop开发环境搭建</span>
            <span class="post-date" title="2020-06-30 18:06:23">2020/06/30</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/06/30/java-install-windows/"
           data-tag="java"
           data-author="沐雨云楼" >
            <span class="post-title" title="jdk开发环境搭建">jdk开发环境搭建</span>
            <span class="post-date" title="2020-06-30 15:09:34">2020/06/30</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/06/30/ai-python-spark-env/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="python spark开发环境搭建">python spark开发环境搭建</span>
            <span class="post-date" title="2020-06-30 12:14:04">2020/06/30</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/06/29/ai-jupyter-notebook/"
           data-tag="标签"
           data-author="沐雨云楼" >
            <span class="post-title" title="jupyter notebook">jupyter notebook</span>
            <span class="post-date" title="2020-06-29 12:29:36">2020/06/29</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/06/26/ai-python-tools/"
           data-tag="tools"
           data-author="沐雨云楼" >
            <span class="post-title" title="python和ai常用工具">python和ai常用工具</span>
            <span class="post-date" title="2020-06-26 09:55:24">2020/06/26</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/06/25/python-tool-buildin-attr/"
           data-tag="attr"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍python内置属性(魔法方法)">👍python内置属性(魔法方法)</span>
            <span class="post-date" title="2020-06-25 11:01:33">2020/06/25</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/06/24/python-tool-buildin-func/"
           data-tag="func"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍python内置函数">👍python内置函数</span>
            <span class="post-date" title="2020-06-24 18:31:59">2020/06/24</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/06/24/python-tool-obj-dict/"
           data-tag="dict"
           data-author="沐雨云楼" >
            <span class="post-title" title="python对象与dict互转">python对象与dict互转</span>
            <span class="post-date" title="2020-06-24 18:15:03">2020/06/24</span>
        </a>
        
        <a  class="大数据 spark "
           href="/blog/2020/06/21/spark-version-3/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="spark3.0新特性">spark3.0新特性</span>
            <span class="post-date" title="2020-06-21 17:40:12">2020/06/21</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/06/21/java-base-domain/"
           data-tag="domain"
           data-author="沐雨云楼" >
            <span class="post-title" title="VO DTO DO PO你都了解吗?">VO DTO DO PO你都了解吗?</span>
            <span class="post-date" title="2020-06-21 09:20:03">2020/06/21</span>
        </a>
        
        <a  class="大数据 spark "
           href="/blog/2020/06/20/spark-data-skew/"
           data-tag="spark"
           data-author="沐雨云楼" >
            <span class="post-title" title="spark数据倾斜及解决方案">spark数据倾斜及解决方案</span>
            <span class="post-date" title="2020-06-20 21:41:12">2020/06/20</span>
        </a>
        
        <a  class="linux nginx "
           href="/blog/2020/06/20/nginx-fast/"
           data-tag="nginx"
           data-author="沐雨云楼" >
            <span class="post-title" title="nginx为何这么快?">nginx为何这么快?</span>
            <span class="post-date" title="2020-06-20 17:55:10">2020/06/20</span>
        </a>
        
        <a  class="架构 "
           href="/blog/2020/06/20/fw-mq-message-missing/"
           data-tag="mq"
           data-author="沐雨云楼" >
            <span class="post-title" title="MQ如何保证消息不丢失?">MQ如何保证消息不丢失?</span>
            <span class="post-date" title="2020-06-20 17:03:18">2020/06/20</span>
        </a>
        
        <a  class="java "
           href="/blog/2020/06/20/java-base-serializable/"
           data-tag="序列化"
           data-author="沐雨云楼" >
            <span class="post-title" title="java序列化">java序列化</span>
            <span class="post-date" title="2020-06-20 16:29:04">2020/06/20</span>
        </a>
        
        <a  class="架构 "
           href="/blog/2020/06/20/fw-distributed-lock-redis-zk/"
           data-tag="lock,redis,zookeeper"
           data-author="沐雨云楼" >
            <span class="post-title" title="分布式锁用redis还是zk?">分布式锁用redis还是zk?</span>
            <span class="post-date" title="2020-06-20 12:09:55">2020/06/20</span>
        </a>
        
        <a  class="java tools "
           href="/blog/2020/06/19/java-tool-jackson/"
           data-tag="jackson"
           data-author="沐雨云楼" >
            <span class="post-title" title="工具类--jackson">工具类--jackson</span>
            <span class="post-date" title="2020-06-19 13:00:45">2020/06/19</span>
        </a>
        
        <a  class="java tools "
           href="/blog/2020/06/19/java-tool-bean-map/"
           data-tag="beanmap"
           data-author="沐雨云楼" >
            <span class="post-title" title="工具类--bean和map互转">工具类--bean和map互转</span>
            <span class="post-date" title="2020-06-19 12:30:14">2020/06/19</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/06/18/java-rest-assured-in-action/"
           data-tag="rest"
           data-author="沐雨云楼" >
            <span class="post-title" title="rest-assured实战">rest-assured实战</span>
            <span class="post-date" title="2020-06-18 17:51:56">2020/06/18</span>
        </a>
        
        <a  class="java test "
           href="/blog/2020/06/17/java_rest_assured_wiki_info/"
           data-tag="rest"
           data-author="沐雨云楼" >
            <span class="post-title" title="rest-assured wiki翻译">rest-assured wiki翻译</span>
            <span class="post-date" title="2020-06-17 20:39:11">2020/06/17</span>
        </a>
        
        <a  class="python tornado "
           href="/blog/2020/06/16/tornado-wtforms/"
           data-tag="wtforms"
           data-author="沐雨云楼" >
            <span class="post-title" title="wtforms表单验证">wtforms表单验证</span>
            <span class="post-date" title="2020-06-16 21:52:33">2020/06/16</span>
        </a>
        
        <a  class="python tornado "
           href="/blog/2020/06/16/tornado-sync-to-async/"
           data-tag="aysnc"
           data-author="沐雨云楼" >
            <span class="post-title" title="tornado同步转异步">tornado同步转异步</span>
            <span class="post-date" title="2020-06-16 21:50:25">2020/06/16</span>
        </a>
        
        <a  class="python tornado "
           href="/blog/2020/06/08/python_tornado_info/"
           data-tag="tornado"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍Tornado入门这一篇足以">👍Tornado入门这一篇足以</span>
            <span class="post-date" title="2020-06-08 20:31:32">2020/06/08</span>
        </a>
        
        <a  class="工具 maven "
           href="/blog/2020/06/07/tool-maven/"
           data-tag="tools,工具"
           data-author="沐雨云楼" >
            <span class="post-title" title="maven常用命令和配置">maven常用命令和配置</span>
            <span class="post-date" title="2020-06-07 16:30:11">2020/06/07</span>
        </a>
        
        <a  class="微服务 springboot "
           href="/blog/2020/06/07/spring-initialzr/"
           data-tag="tools,工具"
           data-author="沐雨云楼" >
            <span class="post-title" title="spring initialzr环境编译发布">spring initialzr环境编译发布</span>
            <span class="post-date" title="2020-06-07 15:06:00">2020/06/07</span>
        </a>
        
        <a  class="windows "
           href="/blog/2020/06/07/windows-cmd/"
           data-tag="tools,工具,命令"
           data-author="沐雨云楼" >
            <span class="post-title" title="windows常用命令和技巧">windows常用命令和技巧</span>
            <span class="post-date" title="2020-06-07 11:39:01">2020/06/07</span>
        </a>
        
        <a  class="工具 github "
           href="/blog/2020/06/07/tool-connect-github/"
           data-tag="github"
           data-author="沐雨云楼" >
            <span class="post-title" title="github无法访问解决办法">github无法访问解决办法</span>
            <span class="post-date" title="2020-06-07 10:08:38">2020/06/07</span>
        </a>
        
        <a  class="微服务 spring "
           href="/blog/2020/06/03/spring-transaction/"
           data-tag="transactional"
           data-author="沐雨云楼" >
            <span class="post-title" title="Transactional注解">Transactional注解</span>
            <span class="post-date" title="2020-06-03 22:09:42">2020/06/03</span>
        </a>
        
        <a  class="java dao "
           href="/blog/2020/06/03/java-jpa-query-multi-param/"
           data-tag="JPA"
           data-author="沐雨云楼" >
            <span class="post-title" title="JPA多条件查询">JPA多条件查询</span>
            <span class="post-date" title="2020-06-03 21:38:04">2020/06/03</span>
        </a>
        
        <a  class="java tools "
           href="/blog/2020/06/02/java-tool-fastjson-bug/"
           data-tag="fastjson"
           data-author="沐雨云楼" >
            <span class="post-title" title="Fastjson远程代码高危漏洞">Fastjson远程代码高危漏洞</span>
            <span class="post-date" title="2020-06-02 22:38:28">2020/06/02</span>
        </a>
        
        <a  class="linux docker "
           href="/blog/2020/06/02/docker-introduction/"
           data-tag="docker"
           data-author="沐雨云楼" >
            <span class="post-title" title="👍docker入门看这一篇就够了">👍docker入门看这一篇就够了</span>
            <span class="post-date" title="2020-06-02 22:22:30">2020/06/02</span>
        </a>
        
        <a  class="面试 "
           href="/blog/2020/06/02/interview-java-question/"
           data-tag="面试"
           data-author="沐雨云楼" >
            <span class="post-title" title="java常见面试题">java常见面试题</span>
            <span class="post-date" title="2020-06-02 22:15:48">2020/06/02</span>
        </a>
        
        <a  class="微服务 "
           href="/blog/2020/06/02/microservice-why/"
           data-tag="微服务"
           data-author="沐雨云楼" >
            <span class="post-title" title="牛逼公司一定要使用微服务？">牛逼公司一定要使用微服务？</span>
            <span class="post-date" title="2020-06-02 21:15:29">2020/06/02</span>
        </a>
        
        <a  class="面试 "
           href="/blog/2020/06/02/interview-company/"
           data-tag="面试"
           data-author="沐雨云楼" >
            <span class="post-title" title="IT互联网公司名单">IT互联网公司名单</span>
            <span class="post-date" title="2020-06-02 20:41:23">2020/06/02</span>
        </a>
        
        <a  class="java 并发 "
           href="/blog/2020/06/02/java-concurrent-aqs/"
           data-tag="java,并发"
           data-author="沐雨云楼" >
            <span class="post-title" title="java并发AQS">java并发AQS</span>
            <span class="post-date" title="2020-06-02 20:01:48">2020/06/02</span>
        </a>
        
        <a  class="ai "
           href="/blog/2020/05/30/ai-learn-catalog/"
           data-tag="ai"
           data-author="沐雨云楼" >
            <span class="post-title" title="AI学习目录">AI学习目录</span>
            <span class="post-date" title="2020-05-30 08:49:39">2020/05/30</span>
        </a>
        
        <a  class="工具 hexo "
           href="/blog/2020/05/29/hexo-theme-math/"
           data-tag="工具,hexo"
           data-author="沐雨云楼" >
            <span class="post-title" title="hexo主题支持MathJax">hexo主题支持MathJax</span>
            <span class="post-date" title="2020-05-29 09:36:46">2020/05/29</span>
        </a>
        
        <a  class="db redis "
           href="/blog/2020/05/28/redis-memory-eliminate/"
           data-tag="redis"
           data-author="沐雨云楼" >
            <span class="post-title" title="Redis的内存淘汰策略">Redis的内存淘汰策略</span>
            <span class="post-date" title="2020-05-28 21:37:04">2020/05/28</span>
        </a>
        
        <a  class="工具 markdowm "
           href="/blog/2020/05/28/markdown-math-express/"
           data-tag="工具,markdowm"
           data-author="沐雨云楼" >
            <span class="post-title" title="markdown数学公式">markdown数学公式</span>
            <span class="post-date" title="2020-05-28 08:02:03">2020/05/28</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/05/21/python_install/"
           data-tag="python"
           data-author="沐雨云楼" >
            <span class="post-title" title="python环境安装">python环境安装</span>
            <span class="post-date" title="2020-05-21 21:37:04">2020/05/21</span>
        </a>
        
        <a  class="python "
           href="/blog/2020/05/21/python_base/"
           data-tag="python"
           data-author="沐雨云楼" >
            <span class="post-title" title="python基本语法">python基本语法</span>
            <span class="post-date" title="2020-05-21 00:00:00">2020/05/21</span>
        </a>
        
        <a  class="其他 "
           href="/blog/2020/05/20/todo-list/"
           data-tag="plan,计划"
           data-author="沐雨云楼" >
            <span class="post-title" title="计划">计划</span>
            <span class="post-date" title="2020-05-20 11:04:19">2020/05/20</span>
        </a>
        
        <a  class="工具 "
           href="/blog/2020/05/20/blog-template/"
           data-tag="模板"
           data-author="沐雨云楼" >
            <span class="post-title" title="博客自定义模板">博客自定义模板</span>
            <span class="post-date" title="2020-05-20 05:20:00">2020/05/20</span>
        </a>
        
    </nav>
</div>

    </div>
    <div class="hide-list">
        <div class="semicircle" data-title="切换全屏 快捷键 s">
            <div class="brackets first"><</div>
            <div class="brackets">&gt;</div>
        </div>
    </div>
</aside>
<div class="post">
    <div class="pjax">
        <article id="post-data-structures-algorithms-graph" class="article article-type-post" itemscope itemprop="blogPost">
    
        <h1 class="article-title">数据结构和算法6-非线性-图</h1>
    
    <div class="article-meta">
        
        
        <span class="author"><a>沐雨云楼</a></span>
        
        
        <span class="book">
            
                <a  data-rel="结构和算法">结构和算法</a>
            
        </span>
        
        
        <span class="tag">
            
            <a class="color1">结构和算法</a>
            
        </span>
        
    </div>
    <div class="article-meta">
        
            发布时间 : <time class="date" title='最后更新: 2020-09-12 21:21:47'>2020-07-04 16:09</time>
        
    </div>
    <div class="article-meta">
        
        <span>字数:3.6k</span>
        
        
        <span id="busuanzi_container_page_pv">
            阅读 :<span id="busuanzi_value_page_pv">
                <span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </span>
        </span>
        
        
        <span class="top-comment" title="跳转至评论区">
            <a href="#comments">
                评论:<span class="count-comment">
                    <span class="spinner">
                      <div class="cube1"></div>
                      <div class="cube2"></div>
                    </span>
                </span>
            </a>
        </span>
        
    </div>
    
    <div class="toc-ref">
    
        <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-图概念"><span class="toc-text">1.图概念</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-1-无向图"><span class="toc-text">1-1.无向图</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-有向图"><span class="toc-text">1-2.有向图</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-图分类"><span class="toc-text">1-3.图分类</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1-3-1-完全图"><span class="toc-text">1-3-1.完全图</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-2-稀疏和稠密图"><span class="toc-text">1-3-2.稀疏和稠密图</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-3-连通图"><span class="toc-text">1-3-3.连通图</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-存储结构"><span class="toc-text">2.存储结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-邻接矩阵"><span class="toc-text">2-1.邻接矩阵</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-链式"><span class="toc-text">2-2.链式</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#2-2-1-邻接表"><span class="toc-text">2-2-1.邻接表</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-图搜索"><span class="toc-text">3.图搜索</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-深度优先搜索"><span class="toc-text">3-1.深度优先搜索</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-2-广度优先搜索"><span class="toc-text">3-2.广度优先搜索</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-最短路径"><span class="toc-text">4.最短路径</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#4-1-最少顶点"><span class="toc-text">4-1.最少顶点</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-2-狄克斯特拉算法"><span class="toc-text">4-2.狄克斯特拉算法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-狄克斯特拉算法实现"><span class="toc-text">5.狄克斯特拉算法实现</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#5-1-顶点定义"><span class="toc-text">5-1.顶点定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-2-边定义"><span class="toc-text">5-2.边定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-3-结果定义"><span class="toc-text">5-3.结果定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-4-算法实现"><span class="toc-text">5-4.算法实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#5-5-测试类"><span class="toc-text">5-5.测试类</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-链接"><span class="toc-text">6.链接</span></a></li></ol>
    
<style>
    .left-col .switch-btn,
    .left-col .switch-area {
        display: none;
    }
    .toc-level-4 i,
    .toc-level-4 ol {
        display: none !important;
    }
</style>
</div>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h2 id="1-图概念"><a href="#1-图概念" class="headerlink" title="1.图概念"></a>1.图概念</h2><p>图是元素之间是多对多的关系，由顶点V集和边E集构成，因此图可以表示成G=(V,E)</p>
<p>图又分为：<strong>无向图</strong>和<strong>有向图</strong>。</p>
<h3 id="1-1-无向图"><a href="#1-1-无向图" class="headerlink" title="1-1.无向图"></a>1-1.无向图</h3><img src="/blog/images/da/da-graph-define-no-direction.png" width="250px">

<p>上图就是无向图，我们可以说这张图中,在无向图中，边<code>(u,v)</code>和边<code>(v,u)</code>是一样的，因此只要记录一个就行了。也就是说方向是无关的。</p>
<ul>
<li>有点集V={1,2,3,4,5,6}</li>
<li>边集E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)}。</li>
</ul>
<h3 id="1-2-有向图"><a href="#1-2-有向图" class="headerlink" title="1-2.有向图"></a>1-2.有向图</h3><img src="/blog/images/da/da-graph-define-direction.png" width="250px">

<p>有向图也很好理解，就是加上了方向性，顶点<code>&lt;u,v&gt;</code>之间的关系和顶点<code>&lt;v,u&gt;</code>之间的关系不同。例如你欠我的钱和我欠你的钱是万万不能混淆的。</p>
<p>下面介绍一些基本名称</p>
<ul>
<li><strong>弧头</strong>：箭头直线的顶点被称为<code>终端点</code>或<code>弧头</code></li>
<li><strong>弧尾</strong>: 无箭头一端的顶点通常被称为<code>初始点</code>或<code>弧尾</code></li>
<li><strong>入度</strong>：对于有向图中的一个顶点V来说,箭头指 V的弧的数量为V的入度, InDegree，记为 ID(V)</li>
<li><strong>出度</strong>：箭头远离V的弧的数量为V的出度，OutDegree，记为OD(V)</li>
<li><strong>路径</strong>：无论是无向图还是有向图，从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径</li>
<li><strong>简单路径</strong>：没有重复顶点的路径称为简单路径。说白了，这一趟路里没有出现绕了一圈回到同一点的情况，也就是没有环。</li>
<li><strong>权</strong>：在某些实际场景中，图中的每条边（或弧）会赋予一个实数来表示一定的含义，这种与边（或弧）相匹配的实数被称为<code>权</code>（如下图）</li>
</ul>
<img src="/blog/images/da/da-graph-define-weight.png" width="380px">

<h3 id="1-3-图分类"><a href="#1-3-图分类" class="headerlink" title="1-3.图分类"></a>1-3.图分类</h3><p>根据不同的特征，图又可分为<strong>完全图</strong>，<strong>连通图</strong>、<strong>稀疏图</strong>和<strong>稠密图</strong>：</p>
<h4 id="1-3-1-完全图"><a href="#1-3-1-完全图" class="headerlink" title="1-3-1.完全图"></a>1-3-1.完全图</h4><ul>
<li><strong>完全图</strong>：各个顶点都与除自身外的其他顶点有关系，这样的无向图称为完全图</li>
<li><strong>有向完全图</strong>: 满足此条件的有向图则称为有向完全图</li>
</ul>
<img src="/blog/images/da/da-graph-category-all.png" width="380px">

<blockquote>
<p>具有n个顶点的完全图，图中边的数量为<code>n(n-1)/2</code>；而对于具有n个顶点的有向完全图，图中弧的数量为<code>n(n-1)</code>。</p>
</blockquote>
<h3 id="1-3-2-稀疏和稠密图"><a href="#1-3-2-稀疏和稠密图" class="headerlink" title="1-3-2.稀疏和稠密图"></a>1-3-2.稀疏和稠密图</h3><ul>
<li><strong>稀疏图</strong>: 图中具有很少的边（或弧），满足 <code>e&lt;nlogn</code></li>
<li><strong>稠密图</strong>: 图中具有很多的边（或弧）<code>e&gt;nlogn</code><blockquote>
<p> e 表示图中边（或弧）的数量，n 表示图中顶点的数量</p>
</blockquote>
</li>
</ul>
<h3 id="1-3-3-连通图"><a href="#1-3-3-连通图" class="headerlink" title="1-3-3.连通图"></a>1-3-3.连通图</h3><p>图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的（不一定要直接连通、间接连通也可以）</p>
<blockquote>
<p>大白话讲: 不存在孤立的顶点(子图)</p>
</blockquote>
<img src="/blog/images/da/da-graph-category-connect-no.png" width="600px">

<blockquote>
<p>其中:a无向图不是连通图。可以分解为3个”最大子图”，它们都满足连通图的性质，因此都是连通分量。</p>
</blockquote>
<p><strong>强连通图</strong></p>
<p>有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图</p>
<img src="/blog/images/da/da-graph-category-connect-strong.png" width="260px">

<p>与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。</p>
<img src="/blog/images/da/da-graph-category-connect-strong-sub.png" width="260px">

<blockquote>
<p>整个有向图虽不是强连通图，但其含有两个强连通分量。</p>
</blockquote>
<h2 id="2-存储结构"><a href="#2-存储结构" class="headerlink" title="2.存储结构"></a>2.存储结构</h2><ul>
<li>邻接矩阵 (二维数组 顺序结构)</li>
<li>邻接表 (链表 链表存储)</li>
</ul>
<h3 id="2-1-邻接矩阵"><a href="#2-1-邻接矩阵" class="headerlink" title="2-1.邻接矩阵"></a>2-1.邻接矩阵</h3><div class="pic_box">
    <div class="pic_parallel">
        <img src="/blog/images/da/da-graph-storage-array-ex1.png" height="350px">
    </div>
    <div class="pic_parallel">
        <img src="/blog/images/da/da-graph-storage-array-ex2.png" height="350px">
    </div>
</div>

<blockquote>
<p>无向图：对角对称</p>
</blockquote>
<p>假定图中顶点数为v,邻接矩阵通过长、宽都为v的二维数组实现，若稀疏图(图中边的数目较少)通过邻接矩阵，会浪费很多内存空间。</p>
<p>使用数组存储图时，需要使用两个数组，</p>
<ul>
<li>一个数组存放图中顶点本身的数据（一维数组）</li>
<li>另外一个数组用于存储各顶点之间的关系（二维数组）。</li>
</ul>
<p>不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：<strong>图</strong>和<strong>网</strong></p>
<blockquote>
<p>图: 包括无向图和有向图；<br>网: 是指带权的图，包括无向网和有向网;</p>
</blockquote>
<h3 id="2-2-链式"><a href="#2-2-链式" class="headerlink" title="2-2.链式"></a>2-2.链式</h3><p>通常，图更多的是采用链表存储，具体的存储方法有3种，分别是<strong>邻接表</strong>、<strong>邻接多重表</strong>和<strong>十字链表</strong>。</p>
<blockquote>
<p>这只介绍下<strong>邻接表</strong>,有兴趣可以自己查下。</p>
</blockquote>
<h4 id="2-2-1-邻接表"><a href="#2-2-1-邻接表" class="headerlink" title="2-2-1.邻接表"></a>2-2-1.邻接表</h4><p>邻接表既适用于存储无向图，也适用于存储有向图</p>
<blockquote>
<p>邻接点: 如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。</p>
</blockquote>
<ul>
<li>邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临界点。</li>
<li>为了便于管理这些链表，通常会将所有链表的头节点存储到数组中</li>
</ul>
<img src="/blog/images/da/da-graph-storage-list-ex1.png" width="750px">


<h2 id="3-图搜索"><a href="#3-图搜索" class="headerlink" title="3.图搜索"></a>3.图搜索</h2><p><strong>分两种方式</strong></p>
<ul>
<li>深度优先搜索: (DFS depth-fisrt-search)，类似tree的先序遍历，可以使用递归和栈方式实现</li>
<li>广度优先搜索: (BFS bredth-fisrt-search)，类似tree的层次遍历，可以使用队列实现</li>
</ul>
<img src="/blog/images/da/da-graph-dfs-bfs-ex1.png" width="800px">

<h3 id="3-1-深度优先搜索"><a href="#3-1-深度优先搜索" class="headerlink" title="3-1.深度优先搜索"></a>3-1.深度优先搜索</h3><p>深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。</p>
<img src="/blog/images/da/da-graph-fs-ex1.png" width="450px">

<blockquote>
<p>a. 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；<br>b. 然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；<br>c. 当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；<br>d. 通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3  邻接点 V6 ，然后 V7 ；<br>e. 由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；<br>f. 最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。</p>
</blockquote>
<p>根据上边的过程，可以得到通过深度优先搜索获得的顶点的遍历次序为：</p>
<blockquote>
<p>V1 -&gt; V2 -&gt; V4 -&gt; V8 -&gt; V5 -&gt; V3 -&gt; V6 -&gt; V7</p>
</blockquote>
<p>从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。<br>然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。<br>访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。</p>
<h3 id="3-2-广度优先搜索"><a href="#3-2-广度优先搜索" class="headerlink" title="3-2.广度优先搜索"></a>3-2.广度优先搜索</h3><p>广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。</p>
<img src="/blog/images/da/da-graph-fs-ex1.png" width="450px">

<blockquote>
<p>a. 假设 V1 作为起始点，遍历其所有的邻接点 V2 和 V3 ，<br>b. 以 V2 为起始点，访问邻接点 V4 和 V5 ，<br>c. 以 V3 为起始点，访问邻接点 V6 、 V7 ，<br>d. 以 V4 为起始点访问 V8 ，以 V5 为起始点，由于 V5 所有的起始点已经全部被访问，所有直接略过，<br>e. V6 和 V7 也是如此。</p>
</blockquote>
<p>V1 为起始点的遍历过程结束后，判断图中是否还有未被访问的点，由于图 1 中没有了，所以整个图遍历结束。遍历顶点的顺序为：</p>
<blockquote>
<p>V1 -&gt; V2 -&gt; v3 -&gt; V4 -&gt; V5 -&gt; V6 -&gt; V7 -&gt; V8</p>
</blockquote>
<h2 id="4-最短路径"><a href="#4-最短路径" class="headerlink" title="4.最短路径"></a>4.最短路径</h2><p>两类最短路径问题：</p>
<ul>
<li>根据顶点树最少而计算出的最小值 (DFS)</li>
<li>根据权重计算出的最小值  (狄克斯特拉算法、弗洛伊德算法)</li>
</ul>
<img src="/blog/images/da/da-graph-shortest.svg" width="650px">

<h3 id="4-1-最少顶点"><a href="#4-1-最少顶点" class="headerlink" title="4-1.最少顶点"></a>4-1.最少顶点</h3><p>最少顶点，对应我们生活中示例，比如乘坐地铁或者公交里最少停站点类似。</p>
<blockquote>
<p>使用深度优先搜索，即可解决问题。可以通过队列方式来实现。</p>
</blockquote>
<h3 id="4-2-狄克斯特拉算法"><a href="#4-2-狄克斯特拉算法" class="headerlink" title="4-2.狄克斯特拉算法"></a>4-2.狄克斯特拉算法</h3><p>根据权重来计算出结果。对应我们生活中示例，比如交通的最短时间、最短路径等。</p>
<p><strong>说明；</strong></p>
<ul>
<li>a.使用两个数组，一个数组<code>S[]</code>存处理过后的顶点，一个数组<code>T[]</code>存未处理过的顶点</li>
<li>b.比如从v1出发，那么就将v1方法到<code>S[v1]</code>中,而T为其他<code>T[v2,v3,v4,v5,v6,v7,v8]</code>，这时对应的权重为无穷大(∞)</li>
<li>c.从v1的出发能到达的顶点，的权重列出来作为<strong>临时权重</strong>，跟<strong>确定权重</strong>的权重比较，选择较小的，并设置其前一节点。</li>
<li>d.接着从<code>T[v2,v3,v4,v5,v6,v7,v8]</code>中找到<strong>确定权重</strong>最小的顶点放到<code>S[]</code>中，所以s变为<code>S[v1,v2]</code></li>
<li>e.继续 从v2出发找到能到达的顶带你，将其权重和和v2的<strong>确定权重</strong>权重相加得到<strong>临时权重</strong>，，跟<strong>确定权重</strong>的权重比较，选择较小的，并设置其前一节点。</li>
<li>f.接着从<code>T[v3,v4,v5,v6,v7,v8]</code>中找到<strong>确定权重</strong>最小的顶点放到<code>S[]</code>中，所以s变为<code>S[v1,v2,v3]</code></li>
<li>重复e、f步骤</li>
</ul>
<img src="/blog/images/da/da-graph-dijkstra-step1.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step2.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step3.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step4.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step5.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step6.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step7.png" width="850px">

<img src="/blog/images/da/da-graph-dijkstra-step8.png" width="850px">

<h2 id="5-狄克斯特拉算法实现"><a href="#5-狄克斯特拉算法实现" class="headerlink" title="5.狄克斯特拉算法实现"></a>5.狄克斯特拉算法实现</h2><h3 id="5-1-顶点定义"><a href="#5-1-顶点定义" class="headerlink" title="5-1.顶点定义"></a>5-1.顶点定义</h3><p>根据上面分析的，写出实现代码，代码里有注释，不多解释了。</p>
<pre><code class="java">public class GNode {

    private Object data;

    public GNode(Object data) {
        this.data = data;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        GNode gNode = (GNode) o;
        return Objects.equals(data, gNode.data);
    }

    @Override
    public int hashCode() {
        return Objects.hash(data);
    }

    @Override
    public String toString() {
        return &quot;GNode{&quot; + &quot;data=&quot; + data + &#39;}&#39;;
    }
}</code></pre>
<h3 id="5-2-边定义"><a href="#5-2-边定义" class="headerlink" title="5-2.边定义"></a>5-2.边定义</h3><pre><code class="java">public class GEdge {

    private int wight;

    private GNode from;

    private GNode to;


    public GEdge(int wight, GNode from, GNode to) {
        this.wight = wight;
        this.from = from;
        this.to = to;
    }

    public int getWight() {
        return wight;
    }

    public void setWight(int wight) {
        this.wight = wight;
    }

    public GNode getFrom() {
        return from;
    }

    public void setFrom(GNode from) {
        this.from = from;
    }

    public GNode getTo() {
        return to;
    }

    public void setTo(GNode to) {
        this.to = to;
    }
}
</code></pre>
<h3 id="5-3-结果定义"><a href="#5-3-结果定义" class="headerlink" title="5-3.结果定义"></a>5-3.结果定义</h3><pre><code class="java">public class GMapResult {

    private Object start;

    private GNode previousNode;

    private GNode selfNode;

    private int weight;

    public GMapResult() {
        this.weight = Integer.MAX_VALUE;
    }

    public GMapResult(Object start, GNode selfNode) {
        this.start = start;
        this.selfNode = selfNode;
        this.weight = Integer.MAX_VALUE;
    }

    public GMapResult(GNode selfNode) {
        this.selfNode = selfNode;
        this.weight = Integer.MAX_VALUE;
    }

    public Object getStart() {
        return start;
    }

    public void setStart(Object start) {
        this.start = start;
    }

    public GNode getPreviousNode() {
        return previousNode;
    }

    public void setPreviousNode(GNode previousNode) {
        this.previousNode = previousNode;
    }

    public GNode getSelfNode() {
        return selfNode;
    }


    public void setSelfNode(GNode selfNode) {
        this.selfNode = selfNode;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return &quot;{ previousNode=&quot; + previousNode + &quot;, selfNode=&quot; + selfNode + &quot;, weight=&quot; + weight + &#39;}&#39;;
    }
}</code></pre>
<h3 id="5-4-算法实现"><a href="#5-4-算法实现" class="headerlink" title="5-4.算法实现"></a>5-4.算法实现</h3><pre><code class="java">public class Dijkstra {

    public static void shortestPath(Object start, Map&lt;GNode, List&lt;GEdge&gt;&gt; gNodeMap) {
        GNode startGNode = new GNode(start);
        List&lt;GNode&gt; sList = new ArrayList&lt;&gt;();
        List&lt;GNode&gt; tList = initTList(startGNode, gNodeMap);

        Map&lt;GNode, GMapResult&gt; gResultMap = initResultMap(startGNode, tList);

        doshortestPath(startGNode, sList, tList, gNodeMap, gResultMap);

        System.out.println(&quot;end&quot;);
    }


    private static void doshortestPath(GNode startNode, List&lt;GNode&gt; sList, List&lt;GNode&gt; tList,
                                       Map&lt;GNode, List&lt;GEdge&gt;&gt; gNodeMap, Map&lt;GNode, GMapResult&gt; gResultMap) {
        while (!tList.isEmpty()) {
            GMapResult minWeightGNodeInT = getMinWeightGNodeInT(tList, gResultMap);

            int tmpMin = 0;

            if (minWeightGNodeInT.getWeight() == Integer.MAX_VALUE) {
                // 将起点从T中移除，加入到S中
                tList.remove(startNode);
                sList.add(startNode);
            } else {
                // 从T中移除，加入到S中
                tList.remove(minWeightGNodeInT.getSelfNode());
                sList.add(minWeightGNodeInT.getSelfNode());
                tmpMin = minWeightGNodeInT.getWeight();
            }

            // 取出s里最后一个元素，对其所有的出边进行遍历
            GNode sEndGNode = sList.get(sList.size() - 1);
            List&lt;GEdge&gt; sEndGNodeOutGedge = gNodeMap.get(sEndGNode);

            if (sEndGNodeOutGedge != null) {
                for (GEdge gEdge : sEndGNodeOutGedge) {
                    GNode to = gEdge.getTo();
                    GMapResult oneResult = gResultMap.get(to);

                    int tmpWeight = tmpMin + gEdge.getWight();

                    if (oneResult.getWeight() &gt; tmpWeight) {
                        oneResult.setPreviousNode(sEndGNode);
                        oneResult.setWeight(tmpWeight);
                    }
                }
            }
        }


        gResultMap.entrySet()
                  .stream()
                  .map(Map.Entry::getValue)
                  .filter(item -&gt; item.getSelfNode() != startNode)
                  .collect(Collectors.toList())
                  .forEach(System.out::println);
    }

    private static GMapResult getMinWeightGNodeInT(List&lt;GNode&gt; tList,
                                                   Map&lt;GNode, GMapResult&gt; gResultMap) {
        GNode gNode = tList.stream().min(Comparator.comparingInt(a -&gt; gResultMap.get(a).getWeight())).get();
        return gResultMap.get(gNode);
    }

    private static Map&lt;GNode, GMapResult&gt; initResultMap(GNode startGNode, List&lt;GNode&gt; tList) {
        return tList.stream().collect(Collectors.toMap(item -&gt; item, item -&gt; new GMapResult(startGNode, item)));
    }

    private static List&lt;GNode&gt; initTList(GNode startGNode, Map&lt;GNode, List&lt;GEdge&gt;&gt; gNodeMap) {

        List&lt;GNode&gt; tList = gNodeMap.entrySet()
                                    .stream()
                                    .map(Map.Entry::getValue)
                                    .flatMap(Collection::stream)
                                    .map(GEdge::getTo)
                                    .distinct()
                                    .collect(Collectors.toList());
        tList.add(startGNode);
        return tList;
    }
}</code></pre>
<h3 id="5-5-测试类"><a href="#5-5-测试类" class="headerlink" title="5-5.测试类"></a>5-5.测试类</h3><pre><code class="java">public class DijkstraTest {
    public static void main(String[] args) {
        Map&lt;GNode, List&lt;GEdge&gt;&gt; gNodeMap = genGraph();
        Object start = &quot;v1&quot;;
        Dijkstra.shortestPath(start, gNodeMap);
    }

    private static Map&lt;GNode, List&lt;GEdge&gt;&gt; genGraph() {
        GNode gNode1 = new GNode(&quot;v1&quot;);
        GNode gNode2 = new GNode(&quot;v2&quot;);
        GNode gNode3 = new GNode(&quot;v3&quot;);
        GNode gNode4 = new GNode(&quot;v4&quot;);
        GNode gNode5 = new GNode(&quot;v5&quot;);
        GNode gNode6 = new GNode(&quot;v6&quot;);
        GNode gNode7 = new GNode(&quot;v7&quot;);
        GNode gNode8 = new GNode(&quot;v8&quot;);

        // 简单起见只用长度来演示
        GEdge gEdge1to2 = new GEdge(3, gNode1, gNode2);
        GEdge gEdge1to3 = new GEdge(5, gNode1, gNode3);
        GEdge gEdge1to4 = new GEdge(6, gNode1, gNode4);
        List&lt;GEdge&gt; gNode1OutEdges = Arrays.asList(gEdge1to2, gEdge1to3, gEdge1to4);

        GEdge gEdge2to3 = new GEdge(1, gNode2, gNode3);
        GEdge gEdge2to5 = new GEdge(7, gNode2, gNode5);
        GEdge gEdge2to6 = new GEdge(4, gNode2, gNode6);
        List&lt;GEdge&gt; gNode2OutEdges = Arrays.asList(gEdge2to3, gEdge2to5, gEdge2to6);

        GEdge gEdge3to4 = new GEdge(1, gNode3, gNode4);
        GEdge gEdge3to6 = new GEdge(2, gNode3, gNode6);
        List&lt;GEdge&gt; gNode3OutEdges = Arrays.asList(gEdge3to4, gEdge3to6);

        GEdge gEdge4to6 = new GEdge(3, gNode4, gNode6);
        GEdge gEdge4to7 = new GEdge(5, gNode4, gNode7);
        List&lt;GEdge&gt; gNode4OutEdges = Arrays.asList(gEdge4to6, gEdge4to7);


        GEdge gEdge5to8 = new GEdge(6, gNode5, gNode8);
        List&lt;GEdge&gt; gNode5OutEdges = Collections.singletonList(gEdge5to8);

        GEdge gEdge6to5 = new GEdge(2, gNode6, gNode5);
        GEdge gEdge6to7 = new GEdge(1, gNode6, gNode7);
        GEdge gEdge6to8 = new GEdge(9, gNode6, gNode8);
        List&lt;GEdge&gt; gNode6OutEdges = Arrays.asList(gEdge6to5, gEdge6to7, gEdge6to8);

        GEdge gEdge7to8 = new GEdge(5, gNode7, gNode8);
        List&lt;GEdge&gt; gNode7OutEdges = Collections.singletonList(gEdge7to8);

        Map&lt;GNode, List&lt;GEdge&gt;&gt; gMap = new HashMap&lt;&gt;();
        gMap.put(gNode1, gNode1OutEdges);
        gMap.put(gNode2, gNode2OutEdges);
        gMap.put(gNode3, gNode3OutEdges);
        gMap.put(gNode4, gNode4OutEdges);
        gMap.put(gNode5, gNode5OutEdges);
        gMap.put(gNode6, gNode6OutEdges);
        gMap.put(gNode7, gNode7OutEdges);
        return gMap;
    }
}</code></pre>
<p><strong>结果：</strong></p>
<img src="/blog/images/da/da-graph-shortest.svg" width="650px">

<img src="/blog/images/da/da-graph-dijkstra-step8.png" width="850px">

<pre><code class="txt">{ previousNode=GNode{data=v6}, selfNode=GNode{data=v7}, weight=7}
{ previousNode=GNode{data=v7}, selfNode=GNode{data=v8}, weight=12}
{ previousNode=GNode{data=v1}, selfNode=GNode{data=v2}, weight=3}
{ previousNode=GNode{data=v2}, selfNode=GNode{data=v3}, weight=4}
{ previousNode=GNode{data=v3}, selfNode=GNode{data=v4}, weight=5}
{ previousNode=GNode{data=v6}, selfNode=GNode{data=v5}, weight=8}
{ previousNode=GNode{data=v3}, selfNode=GNode{data=v6}, weight=6}</code></pre>
<h2 id="6-链接"><a href="#6-链接" class="headerlink" title="6.链接"></a>6.链接</h2><ul>
<li><a href="https://www.cnblogs.com/ssyfj/p/9475148.html" target="_blank" rel="noopener">图—图的存储结构5种</a></li>
<li><a href="https://www.cnblogs.com/ssyfj/p/9495960.html" target="_blank" rel="noopener">图—最短路径-弗洛伊德算法</a></li>
</ul>

      
       <hr><span style="font-style: italic;color: gray;"> 转载请注明来源，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 157162006@qq.com </span>
    </div>
</article>


<p>
    <a  class="dashang" onclick="dashangToggle()">赏</a>
</p>


<div class="article_copyright">
    <p><span class="copy-title">文章标题:</span>数据结构和算法6-非线性-图</p>
    <p><span class="copy-title">字数:</span><span class="post-count">3.6k</span></p>
    <p><span class="copy-title">本文作者:</span><a  title="沐雨云楼">沐雨云楼</a></p>
    <p><span class="copy-title">发布时间:</span>2020-07-04, 16:09:47</p>
    <p><span class="copy-title">最后更新:</span>2020-09-12, 21:21:47</p>
    <span class="copy-title">原始链接:</span><a class="post-url" href="/blog/2020/07/04/data-structures-algorithms-graph/" title="数据结构和算法6-非线性-图">https://iworkh.gitee.io/blog/2020/07/04/data-structures-algorithms-graph/</a>
    <p>
        <span class="copy-title">版权声明:</span><i class="fa fa-creative-commons"></i> <a rel="license noopener" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" title="CC BY-NC-SA 4.0 International" target = "_blank">&#34;署名-非商用-相同方式共享 4.0&#34;</a> 转载请保留原文链接及作者。
    </p>
</div>



    <div id="comments"></div>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">

<script type="text/javascript">
    $.getScript('/blog/js/gitalk.js', function () {
        var gitalk = new Gitalk({
            clientID: 'e4a269e1ae1600031361',
            clientSecret: '6f3f981cbc49dd802fde779697d8f01da3a77981',
            repo: 'iworkh.github.io',
            owner: 'iworkh',
            admin: ['iworkh'],
            id: decodeURI(location.pathname),
            distractionFreeMode: 'true',
            language: 'zh-CN',
            perPage: parseInt('10',10)
        })
        gitalk.render('comments')
    })
</script>




    




    </div>
    <div class="copyright">
        <p class="footer-entry">©2020 iworkh</p>
<!--<p class="footer-entry">Built with <a href="https://hexo.io/" target="_blank">Hexo</a> and <a href="https://github.com/yelog/hexo-theme-3-hexo" target="_blank">3-hexo</a> theme</p>-->

    </div>
    <div class="full-toc">
        <button class="full" data-title="切换全屏 快捷键 s"><span class="min "></span></button>
<button class="post-toc-menu" data-title="打开TOC 快捷键 w"><span class="post-toc-menu-icons"></span></button>
<div class="post-toc"><span class="post-toc-title">目录</span>
    <div class="post-toc-content">

    </div>
</div>
<a class="" id="rocket" ></a>

    </div>
</div>
<div class="acParent"></div>

<div class="hide_box" onclick="dashangToggle()"></div>
<div class="shang_box">
    <a class="shang_close"  onclick="dashangToggle()">×</a>
    <div class="shang_tit">
        <p>喜欢就点赞,疼爱就打赏</p>
    </div>
    <div class="shang_payimg">
        <div class="pay_img">
            <img src="/blog/img/alipay.jpg" class="alipay" title="扫码支持">
            <img src="/blog/img/weixin.jpg" class="weixin" title="扫码支持">
        </div>
    </div>
    <div class="shang_payselect">
        <span><label><input type="radio" name="pay" checked value="alipay">支付宝</label></span><span><label><input type="radio" name="pay" value="weixin">微信</label></span>
    </div>
</div>


</body>
<script src="/blog/js/jquery.pjax.js?v=1.0.1" ></script>

<script src="/blog/js/script.js?v=1.0.1" ></script>
<script>
    var img_resize = 'default';
    /*作者、标签的自动补全*/
    $(function () {
        $('.search').AutoComplete({
            'data': ['@沐雨云楼','@iworkh','#ai','#attr','#aysnc','#beanmap','#bigdecimal','#blog','#chrome','#dict','#dll','#docker','#domain','#fastjson','#func','#git','#github','#hadoop','#hexo','#idea','#iworkh','#jackson','#java','#jdni','#jfinalshell','#joplin','#JPA','#lock','#markdowm','#maven','#mock','#mq','#mycat','#mysql','#nginx','#notebook','#plan','#powermock','#python','#redis','#rest','#sharding-jdbc','#spark','#springboot','#test','#tool','#tools','#tornado','#transactional','#web','#windows','#wtforms','#zookeeper','#分库分表','#分页','#命令','#工具','#并发','#序列化','#微服务','#性能分析','#手册','#有道云','#标签','#模板','#百度云盘','#结构和算法','#计划','#迁移','#面试',],
            'itemHeight': 20,
            'width': 418
        }).AutoComplete('show');
    })
    function initArticle() {
        /*渲染对应的表格样式*/
        
            $(".post .pjax table").addClass("green_title");
        

        /*渲染打赏样式*/
        
        $("input[name=pay]").on("click", function () {
            if($("input[name=pay]:checked").val()=="weixin"){
                $(".shang_box .shang_payimg .pay_img").addClass("weixin_img");
            } else {
                $(".shang_box .shang_payimg .pay_img").removeClass("weixin_img");
            }
        })
        

        /*高亮代码块行号*/
        
        $('pre code').each(function(){
            var lines = $(this).text().trim().split('\n').length, widther='';
            if (lines>99) {
                widther = 'widther'
            }
            var $numbering = $('<ul/>').addClass('pre-numbering ' + widther).attr("unselectable","on");
            $(this).addClass('has-numbering ' + widther)
                    .parent()
                    .append($numbering);
            for(var i=1;i<=lines;i++){
                $numbering.append($('<li/>').text(i));
            }
        });
        

        /*访问数量*/
        
        $.getScript("//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js");
        

        /*代码高亮，行号对齐*/
        $('.pre-numbering').css('line-height',$('.has-numbering').css('line-height'));

        
        
    }

    /*打赏页面隐藏与展示*/
    
    function dashangToggle() {
        $(".shang_box").fadeToggle();
        $(".hide_box").fadeToggle();
    }
    

</script>

<!--加入行号的高亮代码块样式-->

<style>
    pre{
        position: relative;
        margin-bottom: 24px;
        border-radius: 10px;
        border: 1px solid #e2dede;
        background: #FFF;
        overflow: hidden;
    }
    code.has-numbering{
        margin-left: 30px;
    }
    code.has-numbering.widther{
        margin-left: 35px;
    }
    .pre-numbering{
        margin: 0px;
        position: absolute;
        top: 0;
        left: 0;
        width: 20px;
        padding: 0.5em 3px 0.7em 5px;
        border-right: 1px solid #C3CCD0;
        text-align: right;
        color: #AAA;
        background-color: #fafafa;
    }
    .pre-numbering.widther {
        width: 35px;
    }
</style>

<!--自定义样式设置-->
<style>
    
    
    .nav {
        width: 442px;
    }
    .nav.fullscreen {
        margin-left: -442px;
    }
    .nav-left {
        width: 120px;
    }
    
    
    @media screen and (max-width: 1468px) {
        .nav {
            width: 442px;
        }
        .nav.fullscreen {
            margin-left: -442px;
        }
        .nav-left {
            width: 150px;
        }
    }
    
    
    @media screen and (max-width: 1024px) {
        .nav {
            width: 442px;
            margin-left: -442px
        }
        .nav.fullscreen {
            margin-left: 0;
        }
        .nav .hide-list.fullscreen {
            left: 442px
        }
    }
    
    @media screen and (max-width: 426px) {
        .nav {
            width: 100%;
        }
        .nav-left {
            width: 100%;
        }
    }
    
    
    .nav-right .title-list nav a .post-title, .nav-right .title-list #local-search-result a .post-title {
        color: #383636;
    }
    
    
    .nav-right .title-list nav a .post-date, .nav-right .title-list #local-search-result a .post-date {
        color: #5e5e5f;
    }
    
    
    .nav-right nav a.hover, #local-search-result a.hover{
        background-color: #e2e0e0;
    }
    
    

    /*列表样式*/
    
    .post .pjax article .article-entry>ol, .post .pjax article .article-entry>ul, .post .pjax article>ol, .post .pjax article>ul{
        border: #e2dede solid 1px;
        border-radius: 10px;
        padding: 10px 32px 10px 56px;
    }
    .post .pjax article .article-entry li>ol, .post .pjax article .article-entry li>ul,.post .pjax article li>ol, .post .pjax article li>ul{
        padding-top: 5px;
        padding-bottom: 5px;
    }
    .post .pjax article .article-entry>ol>li, .post .pjax article .article-entry>ul>li,.post .pjax article>ol>li, .post .pjax article>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    .post .pjax article .article-entry li>ol>li, .post .pjax article .article-entry li>ul>li,.post .pjax article li>ol>li, .post .pjax article li>ul>li{
        margin-bottom: auto;
        margin-left: auto;
    }
    

    /* 背景图样式 */
    
    


    /*引用块样式*/
    

    /*文章列表背景图*/
    

    
</style>






<div class="mobile-menus-out" >

</div>
<div class="mobile-menus">
    
    
    
    <a class="dynamic-menu " target="_blank"  href="https://pgmanor.gitee.io/blog/">pgmanor</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://www.iworkh.com/manualIt/Category/scopeDev/">iworkh</a>
    
    
    <a class="dynamic-menu " target="_blank"  href="https://gitee.com/iworkh">gitee</a>
    
</div>


<div style="position:absolute; bottom: 0; right: 0;">
    <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=150 height=40 src="//music.163.com/outchain/player?type=2&id=1323150930&auto=0&height=32"></iframe>
</div>

</html>
